package com.javaDemo.ti;

import java.util.ArrayList;
import java.util.List;

/**
 * 递增子序列查找器
 * 
 * @author csy
 * @description 找出数组中所有递增子序列
 * 
 *              解题思路：
 *              1. 使用回溯法遍历所有可能的子序列
 *              2. 使用used数组记录本层已经使用过的数字，避免重复
 *              3. 对于每个位置，可以选择使用或不使用当前数字
 *              4. 当子序列长度大于1时，将其加入结果集
 * 
 *              关键点：
 *              1. 不能排序数组，要保持原始顺序
 *              2. 同一层不能重复使用相同的数字
 *              3. 子序列必须是严格递增的
 * 
 *              时间复杂度：O(2^n)，其中n为数组长度
 *              空间复杂度：O(n)，递归调用栈的深度
 * 
 *              示例：
 *              输入：[4,6,7,7]
 *              输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
 * 
 *              参考：https://leetcode-cn.com/problems/increasing-subsequences/
 */
public class IncreasingSubsequenceFinder {
    // 当前路径（当前正在构建的子序列）
    private static List<Integer> currentPath = new ArrayList<>();

    // 存储所有找到的递增子序列
    private static List<List<Integer>> result = new ArrayList<>();

    /**
     * 查找所有递增子序列
     *
     * @param nums 输入数组
     * @return 所有可能的递增子序列列表
     */
    public static List<List<Integer>> findSubsequences(int[] nums) {
        // 清空之前的结果
        result.clear();
        currentPath.clear();

        // 从索引0开始回溯搜索
        backtrack(nums, 0);
        return result;
    }

    /**
     * 回溯方法，递归构建递增子序列
     *
     * @param nums       输入数组
     * @param startIndex 当前处理的起始索引
     */
    private static void backtrack(int[] nums, int startIndex) {
        // 如果当前路径长度大于1，将其加入结果集
        if (currentPath.size() > 1) {
            result.add(new ArrayList<>(currentPath));
        }

        // 使用数组记录本层使用过的数字，防止同一层重复使用相同数字
        // 因为数字范围在[-100, 100]之间，所以used数组大小为201
        int[] used = new int[201];

        // 从startIndex开始遍历数组
        for (int i = startIndex; i < nums.length; i++) {
            // 如果当前数字小于路径中最后一个数字，或者已经在本层使用过，则跳过
            if ((!currentPath.isEmpty() && nums[i] < currentPath.get(currentPath.size() - 1))
                    || (used[nums[i] + 100] == 1)) {
                continue;
            }

            // 标记当前数字在本层已使用
            used[nums[i] + 100] = 1;

            // 将当前数字加入路径
            currentPath.add(nums[i]);

            // 递归处理下一个位置
            backtrack(nums, i + 1);

            // 回溯，移除最后添加的数字
            currentPath.remove(currentPath.size() - 1);
        }
    }

    /**
     * 测试方法
     */
    public static void main(String[] args) {
        // 测试用例
        int[][] testCases = {
                { 4, 6, 7, 7 },
                { 1, 2, 3, 4, 5 },
                { 1, 1, 1, 1, 1 }
        };

        // 执行测试
        for (int[] nums : testCases) {
            System.out.println("输入数组：" + arrayToString(nums));
            List<List<Integer>> sequences = findSubsequences(nums);
            System.out.println("递增子序列：" + sequences);
            System.out.println();
        }
    }

    /**
     * 辅助方法：将数组转换为字符串
     */
    private static String arrayToString(int[] arr) {
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < arr.length; i++) {
            sb.append(arr[i]);
            if (i < arr.length - 1) {
                sb.append(", ");
            }
        }
        sb.append("]");
        return sb.toString();
    }
}